#include <string>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=316 lang=cpp
 *
 * [316] 去除重复字母
 */

// @lc code=start
class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<bool> used('z' + 1, false);
        vector<int> num('z' + 1, 0);
        string res;
        for (char x: s) num[x]++;
        for (char x: s) {
            if (!used[x]) {
                while (!res.empty() && res.back() > x) {
                    char t = res.back();
                    if (num[t] > 0) {
                        res.pop_back();
                        used[t] = false;
                    } else {
                        break;
                    }
                }
                res.push_back(x);
                used[x] = true;
            }
            num[x] -= 1;
        }
        return res;
    }
};
// @lc code=end

